package com.heima.algorithm.dynamicprogramming;

/**
 * @author 勾新杰
 * @version 1.0
 * @date 2024/11/4 11:00
 */
public class Fibonacci {
     /*
        要点一：
            1、从已知子问题的解，推出当前问题的解
            2、推导过程可以表达为一个数学公式
        要点二：
            1、用一维数组或者二维数组来保存之前的计算结果（可以进一步优化）

        Dynamic Programming - 由 Bellman 提出
        其核心思想是将一个复杂问题分解为多个简单的子问题，通过保存这些子问题的解，避免重复计算，从而提高效率。
     */

    /**
     * 求斐波拉契第n项的值
     * @param n 第n项
     * @return 值
     */
    public static int fibonacci1(int n) {
        int[] dp = new int[Math.max(n + 1, 2)];
        dp[0] = 0;
        dp[1] = 1;
        for (int i = 2; i < dp.length; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }

    /**
     * 求斐波拉契第n项的值，进一步优化
     * @param n 第n项
     * @return 值
     */
    public static int fibonacci2(int n) {
        int two = 0;
        int one = 1;
        if (n == 0){
            return two;
        }
        for (int i = 2; i <= n; i++) {
            int c = two + one;
            two = one;
            one = c;
        }
        return one;
    }
}
